package hotLeetcode;

import org.junit.jupiter.api.condition.DisabledIf;

public class H124Leetcode {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private static int ans = Integer.MIN_VALUE;

    public static int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;

    }

    private static int dfs(TreeNode root) {
        if (root == null) return 0;
        int lVal = dfs(root.left);
        int rVal = dfs(root.right);
        ans = Math.max(ans, rVal + lVal + root.val);
        return Math.max(Math.max(lVal, rVal) + root.val, 0);

    }



    private static int maxSum = Integer.MIN_VALUE;  // 存储全局最大路径和

    public static int maxPathSum2(TreeNode root) {
        // 调用递归函数，计算最大路径和
        maxGain(root);
        return maxSum;
    }

    // 递归函数计算当前节点的最大路径和
    private static int maxGain(TreeNode node) {
        // 递归终止条件：如果当前节点为空，则返回0
        if (node == null) {
            return 0;
        }

        // 计算左子树和右子树的最大路径和
        int leftGain = Math.max(maxGain(node.left), 0);  // 如果左子树的路径和为负数，就不选
        int rightGain = Math.max(maxGain(node.right), 0); // 如果右子树的路径和为负数，就不选

        // 当前节点的最大路径和（包含左子树和右子树）
        int priceNewPath = node.val + leftGain + rightGain;

        // 更新全局最大路径和
        maxSum = Math.max(maxSum, priceNewPath);

        // 返回当前节点的最大路径和（只能选择一个子树的路径和加上当前节点）
        return node.val + Math.max(leftGain, rightGain);
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        H124Leetcode.maxPathSum2(root);
    }

}
